The invention relates to a method for determining a correspondence between the time indicated by the internal clocks of a plurality of machines connected to a network, such as sensors or computers, and also to a method for synchronizing data originating from said machines. These two types of process are intimately linked, the second constituting a direct application of the first.
In this context, ‘synchronizing data’ signifies ordering them chronologically as a function of their time of acquisition; in a more restricted sense, it also signifies ‘date stamping’ these same data values with respect to a unique temporal reference. On the other hand, ‘synchronizing clocks’ signifies forcing the latter to indicate the same time at a given moment.
A method of synchronizing data is necessary, for example, in the field of the validation of automobile driving aid devices. In order to study the effect of these devices on the behavior of a driver, test automobiles are equipped with various sensors connected in a network and allowing information on the vehicle (average speed, acceleration . . . ), on the interaction with other vehicles (distance and relative speed . . . ) and on the behavior of the driver (reaction time, direction of observation . . . ) to be simultaneously acquired. The data values acquired by these various sensors and those recorded by the driving aid devices must be synchronized in order to be exploitable by an ergonomist, and the precision of the synchronization must be better than one millisecond, and preferably better than 100 μs, for data acquisition rates able to reach 1 kHz. At the same time, it is desirable to use standard equipment devices and for the system to be very flexible, allowing the acquisition network to be reconfigured during use, and to be very robust against failures and connection problems.
The most obvious solution to the problem of the synchronization of the data originating from a plurality of devices consists in synchronizing all the clocks. Each device assigns a ‘date stamp’ to the data values it records and, since the clocks are synchronized between one another, all the date stamps are directly comparable. In this context, the problem of determining a correspondence between the local times is not posed, because all these times substantially coincide.
The synchronization of the clocks may be performed in a hardware or software manner: a general introduction to these techniques is provided in the article by J. A. Fonseca and P. Fonseca, ‘An overview of clock synchronization solutions’, 4th IFAC International Symposium, Sicica, Argentina, 2000.
The hardware solutions are based on the use of an external clock signal, common to all the devices. In this way, a very high precision can be obtained, for example by the use of an atomic clock, such as that of the GPS system. On the other hand, these solutions have the drawback of requiring dedicated equipment: devices that are not designed to use an external clock signal cannot be connected to the network.
The software solutions comprise the use of software clocks (variables stored in memory) controlled by the ‘hardware’ clock of each device connected to the network. These software clocks are synchronized in such a manner as to indicate approximately the same time at any moment. Among these solutions, two classes can be further differentiated:                either a single synchronization is performed at the beginning of the session using the network, and it is assumed that the drifts of the clocks can be neglected;        or, re-synchronizations are also performed during use; this is the technique adopted, for example, by the protocol NTP (Network Time Protocol).        
As regards the first class of solutions, the assumption of negligible drifts is difficult to verify, at least for acquisition times of several hours and when commercially available computers are used: the clocks of the latter exhibit drifts that may reach 300 μs/s, or over one second per hour. Replacing these clocks by components of better quality equates to a hardware solution that is costly and not very flexible.
The second class of solutions has a difficulty associated with the monotonicity of the clocks. If, for example, a clock has been gaining relative to the reference time, it will be turned back during the re-synchronization. If a first data value has been recorded immediately prior to the moment of re-synchronization and a second data value immediately afterwards, the time stamp of the second recording pre-dates that of the first and the temporal order of the data is reversed. Moreover, the known algorithms that impose the conservation of the monotonicity of time exhibit a relatively slow convergence.
In any case, basing the synchronization of the data on the synchronization of the clocks, or on the use of a single clock, poses limits to the possibilities for reconfiguring the network of devices. Here is a concrete example of a case where the limits of the known techniques of the prior art can be seen. Considering two machines, X and Y, connected to the same network and whose clocks are kept synchronous by a hardware or software method. At a given moment, the machine Y is disconnected from the network, purposely or because of a connection problem, but continues to record data; finally, the machine Y is reconnected after a certain lapse of time. It can easily be understood that it is not possible to order the data acquired during the period of disconnection chronologically, because the synchronization between the clocks of the machines X and Y is irretrievably lost. For this reason, these methods of synchronization are very sensitive to potential network connection problems. In addition, if during the period of disconnection the machine Y had been connected to a second network also comprising a machine Z, there would be no means of synchronizing the data recorded by X with those recorded by Z. The reconnection of the machine Y is also problematic, especially if it is desired that the monotonicity of its clock be conserved. For this reason, these known synchronization methods pose limits to the possibilities for ‘hot’ reconfiguration (during operation) of the networks to which they are applied.
Another technique known from the prior art is to use temporal markers in order to establish an approximate correspondence between the device local times whose internal clocks are not synchronized. In this case, the synchronization of the data is most often done retroactively, in other words after the end of the recording session, and for this reason it is sometimes referred to as ‘re-synchronization’ of the data.
Such a case frequently arises in the field of multimedia, where it is for example necessary to synchronize images, acquired by a digital camera, with sounds, acquired by an external microphone. In the field of multimedia, the demands in terms of precision are however fairly modest, errors up to around 33 milliseconds (ms) being undetectable by human beings. Several data synchronization techniques used in multimedia applications are described in the article by G. Blakowski and R. Steinmetz, ‘A media synchronization survey: reference model, specification, and case studies’, IEEE J. Selected Areas Commun. 141 (1996), pages 5-35.
These techniques are robust and allow a wide flexibility, but their precision is very limited and insufficient for many applications. Moreover, it is not possible to determine with certainty an upper limit for the amplitude of the synchronization errors committed.
A subject of the present invention is a method for establishing a correspondence between the local times of two or more machines whose clocks are not synchronized.
Another subject of the present invention is such a method, with an improved precision with respect to the prior art.
A further subject of the present invention is such a method, with a known precision modeled by an interval.
A further subject of the present invention is such a method, which is robust against connection problems of the network to which the machines, whose local times are to be made to correspond, are connected.
A further subject of the present invention is such a method, which allows a dynamic reconfiguration of such a network.
A further subject of the present invention is such a method, which allows only standard equipment to be used.
A further subject of the present invention is a method for synchronizing the data recorded by two or more machines, or generated by two or more devices, which does not require synchronization of the clocks of said devices or machines, and which is based on the establishment of a correspondence between the local times of two or more machines whose clocks are not synchronized.
Other objects of the present invention consist in providing such a method with an improved precision relative to the prior art, with a known precision, that is robust against problems of connections of the network to which the machines, whose local times are to be made to correspond, are connected, and/or which allows only standard equipment to be used.
At least one of the aforementioned objects is achieved by means of a method for establishing a correspondence by intervals between the time indicated by a first monotonic clock and the time indicated by a second clock, also monotonic, characterized in that it operates, over at least one temporal range, a first temporal reference common to the first and to the second clock and monotonic over said range, and in that said method comprises the steps of:                a) determining a first temporal interval bounded by a first pair of time values of the first clock and belonging to a first temporal range over which said first temporal reference common to the first and to the second clock exists;        b) determining a second temporal interval bounded by a second pair of time values of the first clock and belonging to a second temporal range over which said first temporal reference common to the first and to the second clock exists;        c) determining, using the common temporal reference, a third temporal interval, bounded by a first pair of time values of the second clock, and containing the first temporal interval;        d) determining, by means of the common temporal reference, a fourth temporal interval, bounded by a second pair of time values of the second clock, and containing said second temporal interval;        e) for any given fifth temporal interval bounded by a third pair of time values of the first clock, calculating a sixth temporal interval, bounded by a third pair of time values of the second clock, and containing said fifth temporal interval, the calculation being performed by interpolation or extrapolation using said first, second, third and fourth intervals.        
In one particular embodiment of the invention, the step c) comprises the operations of:
c1) determining a seventh and of an eighth temporal interval, bounded by a fourth and fifth pair of time values of the second clock, respectively, and belonging to the first temporal range, such that the first temporal interval falls in the range between said seventh and eighth temporal intervals;
c2) determining a first, second and third value of the first common temporal reference, included in said first, seventh and eighth temporal intervals, respectively;
c3) calculating, by interpolation, said third temporal interval, using said first, seventh and eighth temporal intervals and said first, second and third values of the first common temporal reference;
and the step d) comprises the operations of:
d1) determining a ninth and of a tenth temporal interval, bounded by a sixth and seventh pair of time values of the second clock, respectively, and belonging to the second temporal range, such that said second temporal interval falls in the range between said ninth and tenth intervals;
d2) determining a fourth, fifth and sixth value of the first common temporal reference, included in said second, ninth and tenth temporal intervals, respectively;
d3) calculating, by interpolation, said fourth temporal intervals, using said second, ninth and tenth temporal intervals and said fourth, fifth and sixth values of the first common temporal reference.
Preferably, the operation c3) is carried out by replacing said first, second and third values of the common temporal reference by temporal intervals whose width is equal to the discretization of the first common temporal reference over the first temporal range, and the operation d3) is carried out by replacing said fourth, fifth and sixth values of the common temporal reference by temporal intervals whose width is equal to the discretization of the first common temporal reference over the second temporal range.
Advantageously, during the temporal range or ranges over which a first common temporal reference exists, a first reading of the first clock is recorded several times, followed by a reading of the first common temporal reference and, subsequently, by a second reading of the first clock, and independently, a first reading of the second clock is recorded, also several times, followed by a reading of the first common temporal reference and then by a second reading of the second clock, and the operations c1), c2), c3), d1), d2) and d3) are performed using these recordings.
In another particular embodiment of the invention, the step c) comprises the operations of:
c1) determining a seventh and an eighth time value of the second clock belonging to the first temporal range, such that said first temporal interval falls in the range between said seventh and eighth values;
c2) determining a first, second and third interval of values of the first common temporal reference, comprising said first temporal interval and said seventh and eighth time values of the second clock, respectively;
c3) calculating, by interpolation, said third temporal interval, using said first interval of time values of the first clock, said seventh and eighth time values of the second clock and said first, second and third intervals of values of the first common temporal reference;
and the step d) comprises the operations of:
d1) determining ninth and tenth time values of the second clock belonging to the second temporal range, such that said second temporal interval falls in the range between said ninth and tenth values;
d2) determining fourth, fifth and sixth intervals of values of the first common temporal reference, comprising said second temporal interval and said ninth and tenth time values of the second clock;
d3) calculating, by interpolation, said fourth temporal interval, using said second interval of time values of the first clock, said ninth and tenth time values of the second clock and said fourth, fifth and sixth intervals of values of the first common temporal reference.
Preferably, the operations c3) and d3) are carried out by replacing said seventh, eighth, ninth and tenth time values of the second clock by temporal intervals whose width is equal to the discretization of the time of the second clock.
Advantageously, during the temporal range or ranges over which a first common temporal reference exists, a first reading of the first common temporal reference is recorded several times, followed by a reading of the first clock and, subsequently, by a second reading of the first common temporal reference, and independently, a first reading of the first common temporal reference is recorded, also several times, followed by a reading of the second clock and then by a second reading of the first common temporal reference, and the operations c1), c2), c3), d1), d2) and d3) are performed using these recordings.
In particular embodiments of the invention, the aforementioned calculations by interpolation or extrapolation are, more precisely, interpolations or extrapolations that are linear or linear by intervals.
Advantageously, when the first temporal reference common to the first and to the second clock exists over at least two separate temporal ranges and can comprise a rupture in monotonicity from one temporal range to the other, a second monotonic common temporal reference is used in order to resolve the ambiguities resulting from the non-monotonicity of the first common temporal reference.
The invention also relates to a method for synchronizing data recorded and date stamped by a first machine, having a first clock, with respect to the local time of a second machine, having a second clock, characterized in that the date stamping is carried out by associating with each data value recorded by the first machine a fifth temporal interval, bounded by a third pair of time values of the first clock, and in that the synchronization is performed by determining, using a method such as that described hereinabove, a sixth temporal interval, bounded by a third pair of time values of the second clock and containing said fifth temporal interval.
In a particular embodiment of such a data synchronization method, the first common temporal reference is supplied by the clock of a synchronous bus which connects, at least temporarily, said first and second machines.
In a particular embodiment of the invention, such a data synchronization method may be broken down into a first sub-process for recording clock readings, such as that described hereinabove, carried out locally by each machine whose data it is desired to synchronize, and a second process for the synchronization itself, effected by a single machine toward which all the data has been transferred after the termination of the data recording session.